/** 
 *  @file Gdr.c
 *  @brief Implementations of functions required by the GDR programmer
 *          and some of their helpers.
 * @author Matt Stallmann @date 29 Dec 2001
 * $Id: Gdr.c 10 2007-06-28 20:08:57Z mfms $
 */

/*
 *  Copyright (C) 1989, 2001 Matthias Stallmann, Prashant Hebbar.
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include "All.h"

void micro_sleep(int delay)
{
#ifdef USLEEP
  usleep(delay);
#else
#ifndef PROCESSOR_SPEED
#define PROCESSOR_SPEED 1000
#endif
  {int i; for (i = 0; i < delay * PROCESSOR_SPEED; i++);}
#endif
}

void blink_vertex(vertex vx, int count)
{
  int i;

  if (!is_valid_vertex(vx)) {
    fprintf(stderr,"\nblink_vertex: bad vertex %d\n", vx);
    abort();
  }

  for (i=0;i<count;i++) {

    HILITE(vx);
    XFlush(disp);
    micro_sleep(BLINK_RATIO*BLINK_DELAY);
    HILITE(vx);
    XFlush(disp);
    micro_sleep(BLINK_RATIO*BLINK_DELAY);
  }
}/* blink_vertex ends */

void blink_edge(edge ej, int count)
{
  int i;

  if ( ! IS_VALID_EJ( ej ) ) { /* edge exists ?  */
    fprintf(stderr,"\nblink_edge: bad edge pointer\n");
    abort();
  }
  for (i=0;i<count;i++) {
    if (is_highlighted_edge(ej))
      draw_edge( hilite, ej );
    else
      draw_edge( rubber_gc, ej );
    XFlush(disp);
    micro_sleep(BLINK_DELAY);
    if (is_highlighted_edge(ej))
      draw_edge( hilite, ej );
    else
      draw_edge( rubber_gc, ej );
    XFlush(disp);
    micro_sleep(BLINK_DELAY);
  }
} /* blink_edge ends */

void init_display_attributes( void ) {
  vertex v;
  edge e;
  for_all_vertices( v ) {
    char * vl = vertex_label( v );
    un_highlight_vertex( v );
    if( strcmp( vl, "" ) != 0 ) {
      expose_vertex_label( v );
    }
    else {
      hide_vertex_label( v );
    }
    free( vl );
  }
  for_all_edges( e ) {
    char * el = edge_label( e );
    display_edge( e );
    un_highlight_edge( e );
    if( strcmp( el, "" ) != 0 ) {
      expose_edge_label( e );
    }
    else {
      hide_edge_label( e );
    }
    free( el );
  }
  draw_gr();
}

void highlight_vertex(vertex vx)
{
  if (!is_valid_vertex(vx)) {
    fprintf(stderr,"\nhighlight_vertex: bad vertex %d\n", vx);
    abort();
  }
  if (H_L_MSK & V_DB(vx))
    return;
  HILITE(vx);
  /* set the highlight bit */
  V_DB(vx) |= H_L_MSK;
} /* hilight_vertex ends */
   
void un_highlight_vertex(vertex vx)
{
  if (!is_valid_vertex(vx)) {
    fprintf(stderr,"\nunhighlight_vertex: bad vertex %d\n", vx);
    abort();
  }
  if (is_highlighted_vertex(vx)) {
    HILITE(vx);
    /* reset the highlight bit */
    V_DB(vx) &= ~H_L_MSK;
  }
} /* un_highlight_vertex ends */

void highlight_edge(edge ej)
{
  if( ! IS_VALID_EJ( ej ) ) {
    fprintf( stderr, "\nError (highlight_edge): bad edge pointer\n" );
    abort();
  }

  if (E_DB(ej) & H_L_MSK)
    return;

  /* set the highlight bit */
  E_DB(ej) |= H_L_MSK;

  if (!is_displayed_edge(ej)) return; /* no drawing action needed if not
                                         displayed */

  /* erase regular edge and draw highlighted one */
  draw_edge( rubber_gc, ej );
  draw_edge( hilite, ej );
} /* highlight_edge ends */

void un_highlight_edge(edge ej)
{
  if (is_highlighted_edge(ej)) {
    /* reset highlightbit */
    E_DB(ej) &= ~H_L_MSK;

    if (!is_displayed_edge(ej)) return; /* no drawing action needed if not
                                           displayed */

    /* erase highlighted edge and draw regular one */
    draw_edge( hilite, ej );
    draw_edge( rubber_gc, ej );
  }
} /* un_highlight_edge ends */

/* INV (for the following three procedures):
        E_DB(e) & DSP_MSK iff e appears on the display */

int is_displayed_edge(edge e)
     /* PRE: e is a nonempty pointer to a valid edge
        POST: FCTVAL == TRUE iff e appears in the display */
{
  if( ! IS_VALID_EJ( e ) ) {
    fprintf( stderr, "\nError (is_displayed_edge): bad edge pointer\n" );
    abort();
  }
  if (E_DB(e) & DSP_MSK) return(TRUE);
  return(FALSE);
}

void display_edge(edge e)
     /* PRE: e is a valid edge
        POST: e appears in the display and its display bit is set */
{
  if( ! IS_VALID_EJ( e ) ) {
    fprintf( stderr, "\nError (display_edge): bad edge pointer\n" );
    abort();
  }
  if (E_DB(e) & DSP_MSK) return; /* already displayed, no action required */
  E_DB(e) |= DSP_MSK;
  put_edge(e);
}

void hide_edge(edge e)
     /* PRE: e is a valid edge
        POST: e appears in the display and its display bit is set */
{
  if( ! IS_VALID_EJ( e ) ) {
    fprintf( stderr, "\nError (hide_edge): bad edge pointer\n" );
    abort();
  }
  if (!(E_DB(e) & DSP_MSK)) return; /* already hidden, no action required */
  erase_edge(e);
  E_DB(e) &= ~DSP_MSK;
}

/* end of new routines dealing with edge display */

   /*---------------------------------------------------------------
   Changes the label of edge 'ej' to 'label'.
   FUNCTIONS CALLED :
   ---------------------------------------------------------------*/
void change_edge_label(edge ej, char *label)
{
  int len;        /* length of new label */

  if ( ! IS_VALID_EJ( ej ) || label == NULL ) {
    fprintf(stderr,"\nError (change_edge_label): bad edge or label pointer\n");
    abort();
  }

  /* check for length of the label - truncate if too long */
  if ((len = strlen(label)) > LINE_LENGTH) {
    printf(" Label for edge (%2d,%2d) too long. Truncated\n",
           VX_1(ej), VX_2(ej));
    *(label + LINE_LENGTH - 1) = '\0';
  }
  strcpy(LABEL(ej), label);
  XResizeWindow(disp, LWIN(ej),
                2* ELAB_HPAD + XTextWidth(elab_font_struct, label, len),
                elab_height);
  if (is_exposed_edge_label(ej))
    redraw_edge_label(ej);
}/* change_edge_label ends */

/*------------------------------------------------------------
   Changes vertex labels to 'label'.
   OUTPUT : FALSE if label is NULL or vertex is NULL_VERTEX, TRUE
       otherwise.
   FUNCTIONS CALLED :
   ------------------------------------------------------------*/
void change_vertex_label(vertex vx, char *label)
{
  int len;        /* length of new label */

  if (!is_valid_vertex(vx)) {
    fprintf(stderr,"\nchange_vertex_label: bad vertex %d\n", vx);
    abort();
  }
  if (label == NULL) {
    label = "\0";
  }

  /* check for length of the label - truncate if too long */
  if ((len = strlen(label)) > LINE_LENGTH) {
    printf(" Label for vertex %d too long. Truncated\n",vx);
    *(label + LINE_LENGTH - 1) = '\0';
  }
  strcpy(VLABEL(vx), label);
  XResizeWindow(disp, VWIN(vx),
                2 * VLAB_HPAD + XTextWidth(vlab_font_struct, label, len),
                vlab_height);
  if (is_exposed_vertex_label(vx))
    redraw_vertex_label(vx);
} /* change_vertex_label ends */

int max_vertex(void)
{
  return(number_of_vertices-1);
} /* max_vertex ends */

int is_valid_vertex(vertex vx)
{
  if ( (vx >= 0) && (vx <= max_vertex()) )
    return( ! DEL(vx) );
  return( FALSE );
} /* is_valid_vertex ends */

vertex get_a_vertex(void)
{
  vertex i=0;

  while ( i <= max_vertex() )
    if ( is_valid_vertex(i) )
      return(i);
    else
      i++;
  return(NULL_VERTEX);
} /* get_a_vertex ends */

/*------------------------------------------------------------
   Returns TRUE if the vertex_label window for vx is exposed.
   OUTPUT : FALSE if invalid vertex, or, not exposed.
   FUNCTIONS CALLED : is_valid_vertex().
   ------------------------------------------------------------*/
int is_exposed_vertex_label(vertex vx)
{
  if (is_valid_vertex(vx) && (V_DB(vx)&EXP_MSK))
    return(TRUE);
  return(FALSE);
} /* is_exposed_vertex_label ends */

/*------------------------------------------------------------
   Returns TRUE if the edge_label window for ej is exposed.
   OUTPUT : FALSE if invalid edge, or, not exposed.
   FUNCTIONS CALLED :
   ------------------------------------------------------------*/
int is_exposed_edge_label(edge ej)
{
  if( ! IS_VALID_EJ( ej ) ) {
    fprintf( stderr, "\nError (is_exposed_edge_label): bad edge pointer\n" );
    abort();
  }
  if (E_DB(ej)&EXP_MSK)
    return(TRUE);
  return(FALSE);
} /* is_exposed_edge_label ends */

/*------------------------------------------------------------
   Returns TRUE if the vertex vx is highlighted.
   OUTPUT : FALSE if vertex nat highlighted, or, invalid.
   FUNCTIONS CALLED : is_valid_vertex().
   ------------------------------------------------------------*/
int is_highlighted_vertex(vertex vx)
{
  if (is_valid_vertex(vx) && (V_DB(vx)&H_L_MSK))
    return(TRUE);
  return(FALSE);
} /* is_highlighted_vertex ends */

/*------------------------------------------------------------
   Returns TRUE if the ej is highlighted.
   OUTPUT : FALSE if invalid edge, or, not highlighted.
   FUNCTIONS CALLED :
   ------------------------------------------------------------*/
int is_highlighted_edge(edge ej)
{
  if( ! IS_VALID_EJ( ej ) ) {
    fprintf( stderr, "\nError (is_highlighted_edge): bad edge pointer\n" );
    abort();
  }
  if (E_DB(ej)&H_L_MSK)
    return(TRUE);
  return(FALSE);
} /* is_highlighted_edge ends */

void expose_vertex_label(vertex vx)
{
  if (is_valid_vertex(vx) && (!(V_DB(vx) & EXP_MSK))) {
    /* not already exposed */
    XMapRaised(disp, VWIN(vx));
    /* set the expose bit */
    V_DB(vx) |= EXP_MSK;

    /* display current label text */
    redraw_vertex_label(vx);
  }
} /* expose_vertex_label ends */

void hide_vertex_label(vertex vx)
{
  if (is_exposed_vertex_label(vx)) {
    XUnmapWindow(disp,VWIN(vx));
    /* reset the expose bit */
    V_DB(vx) &= ~EXP_MSK;
  }
} /* hide_vertex_label ends */

void expose_edge_label(edge ej)
{
  if( ! IS_VALID_EJ( ej ) ) {
    fprintf( stderr, "\nError (expose_edge_label): bad edge pointer\n" );
    abort();
  }
  if (E_DB(ej) & EXP_MSK)
    return;
  XMapRaised(disp, LWIN(ej));
  /* set the expose bit */
  E_DB(ej) |= EXP_MSK;
  redraw_edge_label(ej);
} /* expose_edge_label ends */

void hide_edge_label(edge ej)
{
  if (is_exposed_edge_label(ej)) {
    XUnmapWindow(disp, LWIN(ej));
    /* reset the expose bit */
    E_DB(ej) &= ~EXP_MSK;
  }
} /* hide_edge_label ends */

edge add_edge(vertex vx1, vertex vx2, char *label)
{
  EJ_NODE *ej_pt;
  edge edg;
  int lx, ly, kn[2][2], len, display;

  /* check validity of vertices */
  if ( ! is_valid_vertex(vx1) || ! is_valid_vertex(vx2) ) {
    fprintf(stderr, "\nInvalid vertex: add_edge(%d,%d,%s)\n", vx1, vx2, label);
    abort();
  }

  /* initialize the knot points */
  if ( vx1 == vx2 )   /* this is a loop */
    get_2_knots( kn );          /* prompt user for 2 knots */
  else
    init_knot( vx1, vx2, kn );  /* calculate knots based on previous edges */

  /* initialize the edge label position: if undirected, then
     in the center, if directed, close to the tail (MS 2-28-92),
     currently 2/3 of the way to first knot (MS 3-10-92) */
  if ( ! direct) {
    lx = (kn[0][0] + kn[1][0])/2;
    ly = (kn[0][1] + kn[1][1])/2;
  }
  else {
    lx = (2 * kn[0][0] + vertex_x(vx1))/3;
    ly = (2 * kn[0][1] + vertex_y(vx1))/3;
  }
  /* check for length of the label - truncate if too long */
  if ( (len = strlen(label)) > LINE_LENGTH ) {
    printf(" Label for edge (%2d,%2d) too long. Truncated\n"
           ,vx1,vx2);
    *(label + LINE_LENGTH - 1) = '\0';
  }
  display = EXP_MSK | DSP_MSK;
  /* create the edge record and insert it into adjacency lists of two
     vertices and the list of all edges */
  ej_pt = create_edge_record( vx1, vx2, label, lx, ly, kn, display);
  edg = add_to_list( ej_pt, ADJ( vx1 ) ); /* canonical pointer for
                                                   edge is one in vx1's adj
                                                   list */
  if ( vx1 != vx2 ) add_to_list( ej_pt, ADJ( vx2 ) );
  add_to_list( ej_pt, all_edges );
  /* Draw the edge on the screen */
  put_edge( edg );
  return(edg);
} /* add_edge ends */

EJ_NODE *create_edge_record( vertex i, vertex id, char *label,
                             int lx, int ly,
                             int (*kn)[2], int display )
{
  EJ_NODE * pt = (EJ_NODE *) malloc( sizeof(EJ_NODE) );
  
  /* fill in the info for the edge node */
  pt->my_first_vertex = i; pt->my_second_vertex = id;
  pt->my_label_x = lx; pt->my_label_y = ly;
  
  pt->my_knots[0][0] = kn[0][0];
  pt->my_knots[0][1] = kn[0][1];
  pt->my_knots[1][0] = kn[1][0];
  pt->my_knots[1][1] = kn[1][1];
  pt->my_display = display;
  
  strcpy(pt->my_label, label);

  create_lab_win(main_canvas, pt);
  return(pt);
} /* create_edge_record() ends */


/*------------------------------------------------------------
   Adds a vertex at x,y with label to the list and draws it on
   the screen. Drawn relative to visible area.
   OUTPUT : vertex id of the newly created vertex.
   FUNCTIONS CALLED : put_vx(), create_vlab_win(),
            get_vx_id().
   ------------------------------------------------------------*/
vertex add_vertex(int x, int y, char *label)
{
  int r_val;                    /* query return value (true if not ^C) */
  char dummy[LINE_LENGTH];            /* for query response (ignored) */
  int len;                      /* length of label */
  vertex new_vx;

  /* check max vertex limit */
  if (number_of_vertices >= MAX_VERTEX) {
    BEEP;
    show_help( OTHER_HELP, TOO_MANY_VERTICES );
    return(NULL_VERTEX);
  }

  /* check for existing vertex at the point */
  while( get_vx_id(x,y) != NULL_VERTEX ) {
    BEEP;
    r_val = query(x, y, "Vertex exists : Hit <RET> & Re-Do", dummy);
    /* if aborted by <Ctrl-c> or attempted redo is not a mouse click */
    if ((r_val==FALSE) || (get_xy_from_mouse(&x,&y)==FALSE))
      return(NULL_VERTEX);
  }

  /* assign new vx_id & increment total #vertices */
  new_vx = number_of_vertices++;

  /* check for length of the label - truncate if too long */
  if ((len = strlen(label))>LINE_LENGTH) {
    printf(" Label for vertex %d too long. Truncated\n", new_vx);
    *(label+len-1) = '\0';
  }

  /* Add to the vx_array[] structure
     ----------------------------------*/

  vx_array[new_vx].my_id  = new_vx;

  XCORD(new_vx) = x;    YCORD(new_vx) = y;
  VLX(new_vx) = x;   VLY(new_vx) = y;
  strcpy(VLABEL(new_vx),label);

  create_vlab_win(main_canvas, new_vx);
  /* clear the delete field  & vertex display byte */
  DEL(new_vx) = FALSE;   V_DB(new_vx) = 0;
  /* initialize the adjacency list */
  vx_array[new_vx].my_adj_list = new_list();
  /* draw the vertex on the screen */
  put_vx(new_vx);
  return(new_vx);
} /* add_vertex ends */

/**
   Moves the vertex vx to position (x,y)
*/
void move_vertex_absolute(vertex vx, int x, int y)
{
  if (is_valid_vertex(vx)) {
    move_vx_ej(vx, x, y);
  }
  else {
    printf("\nWarning (move_vertex_absolute): invalid vertex %d\n", vx);
  }
} /* move_vertex_absolute ends */

/**
   Moves the vertex vx by delta_x,delta_y from its current position.
*/
void move_vertex_relative(vertex vx, int delta_x, int delta_y)
{
  if (is_valid_vertex(vx)) {
    move_vx_ej(vx,XCORD(vx)+delta_x,YCORD(vx)+delta_y);
  }
  else {
    printf("\nWarning (move_vertex_relative): invalid vertex %d\n", vx);
  }
} /* move_vertex_relative ends */

int vertex_x(vertex vx)
{
  if (is_valid_vertex(vx))
    return(XCORD(vx));
  printf("\nWarning (vertex_x): invalid vertex %d\n", vx);
  return 0;
} /* vertex_x ends */

int vertex_y(vertex vx)
{
  if (is_valid_vertex(vx))
    return(YCORD(vx));
  printf("\nWarning (vertex_y): invalid vertex %d\n", vx);
  return 0;
} /* vertex_y ends */

int knot(edge ej, int indx, int x_y)
{
  if ( IS_VALID_EJ( ej ) )
    return(KN(ej,indx,x_y));
  printf("\nWarning from knot(_,%d,%d): null edge\n", indx, x_y);
  return 0;
} /* knot ends */

void move_knot(edge ej, int indx, int delta_x, int delta_y)
{
  int fix_indx, old_x, old_y;

  if ( IS_VALID_EJ( ej ) ) {
    /* select the other knot point */
    fix_indx = (indx)? 0:1;
    /* retain the old values for t_affine */
    old_x = KN(ej,indx,0);
    old_y = KN(ej,indx,1);
    /* erase edge -could erase just 2 seg. tho.. */
    put_edge(ej);

    /* update */
    KN(ej,indx,0) += delta_x;
    KN(ej,indx,1) += delta_y;

    /* transform the label window co-ords */
    if (!direct) {
      /* undirected edge -- label is in center segment */
      t_affine(KN(ej,fix_indx,0),KN(ej,fix_indx,1),old_x,old_y,
               KN(ej,indx,0),KN(ej,indx,1),(&LX(ej)),(&LY(ej)));
    } else if (indx == 0) {
      /* first knot moved on directed edge -- label is in first segment */
      t_affine(XCORD(VX_1(ej)), YCORD(VX_1(ej)), old_x, old_y,
               KN(ej,indx,0), KN(ej,indx,1), (&LX(ej)), (&LY(ej)));
    }

    /* move the window  (centered -- MS 3-2-92) */
    mov_elab_window(ej,LX(ej),LY(ej));

    /* redraw the edge */
    put_edge(ej);
  } /* edge is not null */
  else {
    printf("\nWarning from move_knot(_,%d,%d,%d): null edge\n", indx,
           delta_x, delta_y);
  }
} /* mov_knot ends */

int window_width_height(int w_h)
{
  Window    root;
  unsigned int depth, width, height, bw;
  int x, y;

  XGetGeometry(disp, main_canvas, &root, &x, &y, &width, &height, &bw, &depth);
  if (w_h)
    return(width);
  return(height);
} /* window_width ends */

/*------------------------------------------------------------
   Waits for a button click in the main window, and
   returns the co_ords in pointers ax,ay. Beeps on error. <Cntrl-C>
   aborts this function with FALSE as the return value.
   Postion relative to the visible area.
   OUTPUT :
   FUNCTIONS CALLED :
   ------------------------------------------------------------*/
int get_xy_from_mouse(int *ax, int *ay) {
  XEvent l_ev;
  int more = TRUE;

  while (more) {
    XNextEvent(disp, &l_ev);
    if (handle_background_event(l_ev)) continue;

    /* Abort it if invoked by error ... */
    if( (l_ev.type == KeyPress) && (l_ev.xkey.state == ControlMask) )
      return(FALSE);
    if( (l_ev.WIN == main_canvas) && (l_ev.type == ButtonPress)
        && (l_ev.BUT == 1) ) {
      *ax = l_ev.XC;
      *ay = l_ev.YC;
      more = FALSE;
    }
    else
      BEEP;
  }
  return(TRUE);
} /* get_xy_from_mouse ends */

/* -------------------------------------------------------
    select_vertex: returns the id of a vertex selected by the user with
    the mouse.  Returns NULL_VERTEX if user types 'Q' or 'q'
    (added 8-26-91, MS)
    ---------------------------------------------------------*/
vertex select_vertex(void)
{
  XEvent  local_event;
  char    ans[3]; /* for XLookupString -- not used here */
  KeySym  key; /* return parameter for XLookupString */
  vertex  cur_id; /* id of vertex */

  show_help( OTHER_HELP, SELECT_VERTEX );
  while (TRUE) {  /* wait until vertex selected or 'Q' or 'q' pressed */
    XNextEvent(disp, &local_event);
    if (handle_background_event(local_event)) continue;

    if ((local_event.WIN == main_canvas) && (local_event.type == ButtonPress)
        && (local_event.BUT==1)) {
      cur_id = get_vx_id(local_event.XC,local_event.YC);
      if (is_valid_vertex(cur_id)) return(cur_id);
      else BEEP;
    }
    else if ((local_event.WIN == main_canvas)
             && (local_event.type == KeyPress)) {
      /* 3 is the length of buffer 'ans'
         0 is to disable 'Compose Status' */
      XLookupString((XKeyEvent *)&local_event,ans,3,&key,0);
      /* return NULL_VERTEX if 'q' or 'Q' pressed */
      if ((key == XK_q) || (key == XK_Q)) return(NULL_VERTEX);
      else BEEP;
    }
  }
} /* select_vertex ends */

void delete_vertex(vertex vx)
{
  edge current, next;

  if (!is_valid_vertex(vx)) {
    fprintf(stderr,"\nblink_vertex: bad vertex %d\n", vx);
    abort();
  }

  current = V_FIRST(vx);
  while ( current != NULL_EDGE ) {
    next = LNK( current );      /* save pointer to next item before current
                                 gets blown away */
    delete_edge( current );
    current = next;
  }
  free( vx_array[vx].my_adj_list );
  vx_array[vx].my_adj_list = NULL;

  /* erase the vx from the display & set delete marker */
  /* first get rid of label */
  V_DB(vx) &= ~EXP_MSK;
  XDestroyWindow( disp, VWIN(vx) );
  put_vx( vx );                 /* erase vertex */
  vx_array[vx].i_am_deleted = TRUE;
} /* delete_vertex ends */

void clear_graph( int st_vx, int end_vx )
{
  vertex i;                     /* current vertex */
  for ( i = st_vx; i < end_vx; ++i ) {
    if ( DEL(i) )
      continue;      
    delete_vertex( i );
  } /* for i */
} /* clear_graph ends */

void delete_edge(edge pt)
{
  vertex id1, id2;              /* two endpoints of the edge */
  EJ_NODE * edge_ptr;           /* pointer to the actual edge record */

  /* check for invalid (null) edge */
  if ( !IS_VALID_EJ(pt) ) {
    printf("\nWarning (delete_edge): attempt to delete null/bad edge\n");
    return;
  }

  /* get the two endpoints of the edge (and make sure they're valid) */
  id1 = VX_1(pt); id2 = VX_2(pt);
  if ( !is_valid_vertex(id1) || !is_valid_vertex(id2) ) {
    fprintf(stderr, "\nError (delete_edge): invalid endpoint (%d,%d)\n",
            id1, id2);
    abort();
  }
  /* screen update */
  erase_edge(pt);
  XDestroyWindow(disp,LWIN(pt));
  /* get actual edge record and remove it from the lists it belongs in;
     then deallocate it */
  edge_ptr = get_edge_record( pt );
  remove_from_list( edge_ptr, ADJ( id1 ) );
  if ( id1 != id2 ) remove_from_list( edge_ptr, ADJ( id2 ) );
  remove_from_list( edge_ptr, all_edges );
  free( edge_ptr );
} /* delete_edge() ends */

/*-------------------------------------------------------------
   Queries the user with a message prompt. Answer to be terminated
   by a <CR>. Returns FALSE if aborted by <Ctrl-c>, else returns
   TRUE.

   BUGS: 1. expose events for other windows are not handled properly
         2. cursor gets out of synch if it is moved out of query
            window and back in
   --------------------------------------------------------------*/
int query(int x, int y, char *msg, char *ans)
{
  int i;
  Window qwin;
  char   more=TRUE, ch[4];
  char   r_val=TRUE; /* return value */
  KeySym key;
  XEvent q_ev;

  /* adjust position if position is out of bounds */
  if ( x > window_width() - Q_RIGHT_MARGIN )
    x = window_width() - Q_RIGHT_MARGIN;
  if ( y > window_height() - Q_BOTTOM_MARGIN )
    y = window_height() - Q_BOTTOM_MARGIN;
  if ( x < Q_LEFT_MARGIN ) x = Q_LEFT_MARGIN;
  if ( y < Q_TOP_MARGIN ) y = Q_TOP_MARGIN;

  qwin = XCreateSimpleWindow(disp, main_canvas, x, y,
                             strlen(msg) * CH_W + 2 * HPAD, 3 * (CH_H + VPAD),
                             1, black, white);
  XSelectInput(disp, qwin, OwnerGrabButtonMask | KeyPressMask | ExposureMask);
  XDefineCursor(disp, qwin, label_curs);
  XWarpPointer(disp, None, qwin, 0, 0, 0, 0, Q_HPAD + CH_W, 30);
  XMapRaised(disp, qwin);
  XDrawString(disp, qwin, rubber_gc, HPAD, CH_H, msg, strlen(msg));
  XFlush(disp);

  ans[0] = '\0';
  i = 0;
  while (more) {
    XNextEvent(disp,&q_ev);
    if (handle_background_event(q_ev)) continue;

    if (q_ev.type == KeyPress){
      /* check for <Cntrl-C> */
      if (q_ev.xkey.state == ControlMask)
        more = r_val = FALSE;
      XDrawString(disp, qwin, rubber_gc, Q_HPAD,
                  2 * (CH_H + VPAD), ans, strlen(ans));
      XLookupString((XKeyEvent *)&q_ev, ch, 3, &key, 0);
      if (key == XK_Return){
        more = FALSE;
        continue;
      }  
      else if ((key == XK_Delete) || (key == XK_BackSpace)) {
        if (i) {
          i--;
          XWarpPointer(disp, None, None, 0, 0, 0, 0, -CH_W, 0);
        }
      }
      else if (i < LINE_LENGTH-1)
        if ((key > XK_space) && (key < XK_asciitilde)) {
          ans[i] = ch[0];
          XWarpPointer(disp,None,None,0,
                       0,0,0,CH_W,0);
          i++;
        }
      ans[i] = '\0';
      XDrawString(disp, qwin, rubber_gc, Q_HPAD,
                  2 * (CH_H + VPAD), ans, strlen(ans));
    }
    else if (q_ev.type == Expose) {
      if (q_ev.xexpose.window == qwin) {
        /* expose event for query window -> redraw current qwin contents */
        XClearWindow(disp, qwin);
        XDrawString(disp, qwin, rubber_gc, HPAD, CH_H, msg, strlen(msg));
        XDrawString(disp, qwin, rubber_gc, Q_HPAD,
                    2 * (CH_H + VPAD), ans, strlen(ans));
      }
    }
    else
      BEEP;
  } /* while more */

  XUnmapWindow(disp,qwin);
  XDestroyWindow(disp,qwin);
  /* no <Cntrl-C> was hit and query completed */
  return(r_val);

} /* query ends */

/*------------------------------------------------------------
   Returns the first edge from a list of all edges in the graph.
   OUTPUT : NULL_EDGE on error.
   FUNCTIONS CALLED :
   NOTE: Can be made a Macro.
   ------------------------------------------------------------*/
edge first_edge(void)
{
  return(first_on_list(all_edges));
} /* first_edge ends */

/*------------------------------------------------------------
   Returns the next edge after 'ej' from the list of all edges in
   the graph.
   OUTPUT : NULL_EDGE on error.
   FUNCTIONS CALLED :
   ------------------------------------------------------------*/
edge next_edge(edge edj)
{
  if ( IS_VALID_EJ(edj) )
    return( NXT(edj) );
  printf("Warning (next_edge): null/bad edge\n");
  return(NULL_EDGE);
} /* next_edge ends */

/*--------------------------------------------------------------
   Returns the other vertex of the edge 'ej'.
   Error if the vx is not one of the vertices in the edge,
     or if ej is a NULL_EDGE.
   --------------------------------------------------------------*/
vertex other_vertex(vertex vx, edge ej)
{
  if (ej == NULL_EDGE) { /* added this case 8-12-91 (MS) */
    fprintf(stderr,"\nError (other_vertex): null edge (vx = %d)\n", vx);
    abort();
  }
  if (VX_1(ej)==vx)
    return(VX_2(ej));
  else if (VX_2(ej)==vx)
    return(VX_1(ej));
  else {                /* changed this to error 8-13-91 (MS) */
    fprintf(stderr,
            "\nError (other_vertex): vertex %d not an endpoint, ej = (%d,%d)\n",
            vx, VX_1(ej), VX_2(ej));
    abort();
  }
} /* other_vertex ends */

/*------------------------------------------------------------
   Used for first_in_edge() & first_out_edge(). Returns the first
   in edge for vertex 'vx' if 'in' is TRUE, else returns the first
   out edge.
   OUTPUT :
   FUNCTIONS CALLED :
   ------------------------------------------------------------*/
edge first_in_out_edge(vertex vx, int in)
{
  edge   lpt;
  vertex i_o_vx;

  if (!is_valid_vertex(vx)) {
    printf("\nWarning (first_in_out_edge): invalid vertex %d\n", vx);
    return(NULL_EDGE);
  }

  /* get the first edge linked to the vertex */
  lpt = V_FIRST( vx );
  /* get to the req. edge if digraph: the first edge with vx
     as head if in-edge needed, otherwise the first edge with vx
     as tail */
  /* loop modified (MS 5-29-90) */
  if (direct)
    while ( lpt != NULL_EDGE ) {
      i_o_vx = (in) ? VX_2(lpt) : VX_1(lpt);
      if ( i_o_vx == vx )
        return (lpt);
      lpt = NXT( lpt );
    }
  /* here if lpt is null or if direct is false */
  return( lpt );
} /* first_in_out_edge ends */

/*------------------------------------------------------------
   Used for next_in_edge() & next_out_edge(). If 'in' is TRUE,
   this returns the next in_edge, else it returns the next out_
   edge, from vertex 'vx' after the edge 'ej'.
   OUTPUT : the required edge if any or the null edge.
   FUNCTIONS CALLED : other_vertex(), get_ej_atvx(), get_nxt_ej().
   CAVEAT : Works only for edges obtained by first_in_out_egde().
      Meant to be used for loops.
   ------------------------------------------------------------*/
edge next_in_out_edge(vertex vx, edge edj, char in)
{
  vertex i_o_vx;
  edge   lpt;

  if ( ! is_valid_vertex(vx) ) {
    printf("\nWarning (next_in_out_edge): invalid vertex %d\n", vx);
    return(NULL_EDGE);
  }

  lpt = NULL_EDGE;
  if ( IS_VALID_EJ( edj ) ) {
    /* get the next edge */
    lpt = NXT( edj );
    /* get to the req. edge if digraph: the first edge with vx
       as head if in-edge needed, otherwise the first edge with vx
       as tail */
    /* loop modified (MS 5-29-90) */
    if (direct)
      while ( lpt != NULL_EDGE ) {
        i_o_vx = (in) ? VX_2(lpt) : VX_1(lpt);
        if ( i_o_vx == vx )
          return (lpt);
        lpt = NXT( lpt );
      }
  } /* If Not Null Edge */
  else {
    printf("\nWarning (next_in_out_edge): null edge vx = %d\n", vx);
    return(NULL_EDGE);
  }
  return(lpt);
} /* next_in_out_edge ends */

char * vertex_label(vertex vx)
{
  char *str;                    /* value to be returned (allocated) */
  char *current_label;          /* the label (or a standin) */

  if (is_valid_vertex(vx)) {
    current_label = VLABEL(vx);
  }
  else {
    printf("\nWarning (vertex_label): invalid vertex %d\n", vx);
    current_label = "";
  }
  str = calloc(strlen(current_label) + 1, sizeof(char));
  strcpy(str, current_label);
  return(str);
} /* vertex_label ends */

char * edge_label( edge ej )
{
  char *str;                    /* value to be returned (allocated) */
  char *current_label;          /* the label (or a standin) */

  if ( IS_VALID_EJ( ej ) ) {
    current_label = LABEL(ej);
  }
  else {
    printf("\nWarning (edge_label): null edge\n");
    current_label = "";
  }
  str = calloc(strlen(current_label) + 1, sizeof(char));
  strcpy(str, current_label);
  return(str);
} /* edge_label ends */

/* moves label of edge e to a position centered at (x,y) */
void move_edge_label(edge e, int x, int y)
{
  LX(e) = x;
  LY(e) = y;
  mov_elab_window(e,x,y);
}

vertex head(edge ej)
{
  if ( IS_VALID_EJ( ej ) )
    return(VX_2(ej));
  printf("\nWarning (head): null edge\n");
  return(NULL_VERTEX);
} /* head ends */

vertex tail(edge ej)
{
  if ( IS_VALID_EJ( ej ) )
    return(VX_1(ej));
  printf("\nWarning (head): null edge\n");
  return(NULL_VERTEX);
} /* tail ends */

/** end of Gdr.c **/

/*  [Last modified: 2007 06 28 at 19:15:59 GMT] */
